package com.leetcode.algorithm.y18.m05;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * leetcode-cn.com
 * 371. 两整数之和
 * 401. 二进制手表
 * 461. 汉明距离
 * 476. 数字的补数
 * 693. 交替位二进制数
 * 762. 二进制表示中质数个计算置位
 * @author: jie.deng
 * @time: 2018年5月30日 下午1:18:48
 */
public class MySolution0530 {

	/**
	 * 371. 两整数之和
	 * 
	 * 不使用运算符 + 和-，计算两整数a 、b之和。
	 * 示例： 若 a = 1 ，b = 2，返回 3。
	 * 
	 * @param a
	 * @param b
	 * @return
	 */
	public int getSum(int a, int b) {
		char[] charsA = Integer.toBinaryString(a).toCharArray();
		char[] charsB = Integer.toBinaryString(b).toCharArray();
		int lenA = charsA.length;
		int lenB = charsB.length;
		int len = Math.max(lenA, lenB);
		if (lenA != lenB) {
			char[] chars = new char[len];
			Arrays.fill(chars, '0');
			if (lenA < len) {
				System.arraycopy(charsA, 0, chars, len - lenA, lenA);
				charsA = chars;
			} else if (lenB < len) {
				System.arraycopy(charsB, 0, chars, len - lenB, lenB);
				charsB = chars;
			}
		}
		char[] chars = new char[len];
		int i = 1;
		int carry = 0; // 不进位
		while (i <= len) {
			int chA = (int) (charsA[len - i] - '0');
			int chB = (int) (charsB[len - i] - '0');
			int sum = chA ^ chB;
			chars[len - i] = (char) (sum ^ carry + '0');
			carry = (chA & chB) | (sum & carry);
			i++;
		}
		if (carry != 0 && chars.length != 32) {	//chars.length=32时溢出
			char[] chs = new char[len + 1];
			System.arraycopy(chars, 0, chs, 1, len);
			chs[0] = (char) (carry + '0');
			chars = chs;
		}
		String str = "";
		if (chars.length == 32 && chars[0] == '1') {
			str = "-";
			// 按位取反加1
			int j = 0;
			for (; j < chars.length; j++) {
				chars[j] = chars[j] == '0' ? '1' : '0'; // 按位取反
			}
			j = chars.length - 1;
			while (chars[j] == '1') {
				chars[j] = '0'; // 加1
				j--;
			}
			chars[j] = '1';
		}
		str = str + new String(chars);
		return Integer.parseInt(str, 2);
	}

	public int getSumBit(int a, int b) {
		char[] charsA = Integer.toBinaryString(a).toCharArray();
		char[] charsB = Integer.toBinaryString(b).toCharArray();
		int lenA = charsA.length;
		int lenB = charsB.length;
		char[] charsL = new char[32];
		Arrays.fill(charsL, '0');
		System.arraycopy(charsA, 0, charsL, 32 - lenA, lenA);
		char[] charsR = new char[32];
		Arrays.fill(charsR, '0');
		System.arraycopy(charsB, 0, charsR, 32 - lenB, lenB);

		char[] chars = new char[32];
		int carry = 0; // 不进位
		for (int i = 31; i >= 0; i--) {
			// 全加器
			int chL = (int) (charsL[i] - '0');
			int chR = (int) (charsR[i] - '0');
			int sum = chL ^ chR;
			chars[i] = (char) (sum ^ carry + '0');
			carry = (chL & chR) | (sum & carry);
		}
		if (chars[0] == '1') {
			// 按位取反
			for (int i = 0; i < 32; i++) {
				chars[i] = (char) ((chars[i] ^ '1') + '0');
			}
			return -Integer.parseInt(new String(chars), 2) - 1;
		} else {
			return Integer.parseInt(new String(chars), 2);
		}
	}
	public int getSumSolution(int a, int b) {
		int sum = a ^ b;
		int carry = ((a & b) << 1);
		if (carry == 0) {
			return sum;
		} else {
			return getSumSolution(sum, carry);
		}
	}
	
	/**
	 * 401. 二进制手表
	 * 
	 * 二进制手表顶部有 4 个 LED 代表小时（0-11），底部的 6 个 LED 代表分钟（0-59）。 
	 * 每个 LED 代表一个 0 或 1，最低位在右侧。 
	 * 
	 * 给定一个非负整数 n 代表当前 LED 亮着的数量，返回所有可能的时间。 
	 * 
	 * 案例:
	 * 输入: n = 1 
	 * 返回: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]
	 * 
	 * 注意事项:
	 * 输出的顺序没有要求。 
	 * 小时不会以零开头，比如 “01:00” 是不允许的，应为 “1:00”。 
	 * 分钟必须由两位数组成，可能会以零开头，比如 “10:2” 是无效的，应为 “10:02”。
	 * 
	 * @param num
	 * @return
	 */
	public List<String> readBinaryWatch(int num) {
		if (num >= 10) {
			return Arrays.asList();
		}
		Map<Integer, List<String>> hourMap = new HashMap<Integer, List<String>>();
		for (int i = 0; i <= 4; i++) {
			List<String> list = new ArrayList<String>();
			hourMap.put(i, list);
		}
		for (int i = 0; i <= 11; i++) {
			int len = Integer.toBinaryString(i).replaceAll("0", "").length();
			hourMap.get(len).add("" + i);
		}

		Map<Integer, List<String>> minMap = new HashMap<Integer, List<String>>();
		for (int i = 0; i <= 6; i++) {
			List<String> list = new ArrayList<String>();
			minMap.put(i, list);
		}
		for (int i = 0; i <= 59; i++) {
			int len = Integer.toBinaryString(i).replaceAll("0", "").length();
			minMap.get(len).add(i > 9 ? "" + i : "0" + i);
		}

		List<String> list = new ArrayList<String>();
		for (int i = 0; i <= num; i++) {
			if (i > 4 || num - i > 6) {
				continue;
			}
			List<String> listHour = hourMap.get(i);
			List<String> listMin = minMap.get(num - i);
			if (listHour.size() > 0 && listMin.size() > 0) {
				for (String hour : listHour) {
					for (String min : listMin) {
						list.add(hour + ":" + min);
					}
				}
			}
		}

		return list;
	}

	/**
	 * 461. 汉明距离
	 *	两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
	 *	给出两个整数 x 和 y，计算它们之间的汉明距离。
	 *
	 *	注意：
	 *	0 ≤ x, y < 2的31次方.
	 *	示例:
	 *	输入: x = 1, y = 4
	 *	输出: 2
	 *	解释:
	 *	1   (0 0 0 1)
	 *	4   (0 1 0 0)
	 *	       ↑   ↑
	 *	上面的箭头指出了对应二进制位不同的位置。
	 * @param x
	 * @param y
	 * @return
	 */
    public int hammingDistance(int x, int y) {
//    	int z = x ^ y;
//    	return Integer.toBinaryString(z).replaceAll("0", "").length();
		char[] charsA = Integer.toBinaryString(x).toCharArray();
		char[] charsB = Integer.toBinaryString(y).toCharArray();
		int lenA = charsA.length;
		int lenB = charsB.length;
		int len = Math.max(lenA, lenB);
		if (lenA != lenB) {
			char[] chars = new char[len];
			Arrays.fill(chars, '0');
			if (lenA < len) {
				System.arraycopy(charsA, 0, chars, len - lenA, lenA);
				charsA = chars;
			} else if (lenB < len) {
				System.arraycopy(charsB, 0, chars, len - lenB, lenB);
				charsB = chars;
			}
		}
		int count = 0;
		for (int i = 0; i < len; i++) {
			count += charsA[i] ^ charsB[i];
		}
		return count;
    }
    
    /**
	 * 476. 数字的补数
	 * 给定一个正整数，输出它的补数。补数是对该数的二进制表示取反。
	 * 
	 * 注意:
	 * 给定的整数保证在32位带符号整数的范围内。 
	 * 你可以假定二进制数不包含前导零位。 
	 * 
	 * 示例 1:
	 * 输入: 5 
	 * 输出: 2 
	 * 解释: 5的二进制表示为101（没有前导零位），其补数为010。所以你需要输出2。 
	 * 
	 * 示例 2:
	 * 输入: 1 
	 * 输出: 0 
	 * 解释: 1的二进制表示为1（没有前导零位），其补数为0。所以你需要输出0。
	 * 
	 * @param num
	 * @return
	 */
	public int findComplement(int num) {
		int len = Integer.toBinaryString(num).length(); 
		return num ^ 0xffffffff << (32-len) >>> (32-len);
	}
	public int findComplement2(int num) {
		int pow = 1;
		while (num > pow) {
			pow <<= 1;
			pow |= 1;
		}
		return num ^ pow;
	}
    
	/**
	 * 693. 交替位二进制数
	 * 
	 * 给定一个正整数，检查他是否为交替位二进制数：换句话说，就是他的二进制数相邻的两个位数永不相等。
	 * 
	 * 示例 1:
	 * 输入: 5 输出: True 解释: 5的二进制数是: 101 
	 * 
	 * 示例 2:
	 * 输入: 7 输出: False 解释: 7的二进制数是: 111 
	 * 
	 * 示例 3:
	 * 输入: 11 输出: False 解释: 11的二进制数是: 1011 
	 * 
	 * 示例 4:
	 * 输入: 10 输出: True 解释: 10的二进制数是: 1010
	 * 
	 * @param n
	 * @return
	 */
	public boolean hasAlternatingBits(int n) {
		int m = n << 1;
		if ((m & n) == 0) {
			int l = m ^ n;
			l = l >>> 1;
			return (l & (l + 1)) == 0;
		}
		return false;
	}
    
	/**
	 * 762. 二进制表示中质数个计算置位
	 *	给定两个整数 L 和 R ，找到闭区间 [L, R] 范围内，计算置位位数为质数的整数个数。
	 *	（注意，计算置位代表二进制表示中1的个数。例如 21 的二进制表示 10101 有 3 个计算置位。还有，1 不是质数。）
	 *	
	 *	示例 1:
	 *	输入: L = 6, R = 10
	 *	输出: 4
	 *	解释:
	 *	6 -> 110 (2 个计算置位，2 是质数)
	 *	7 -> 111 (3 个计算置位，3 是质数)
	 *	9 -> 1001 (2 个计算置位，2 是质数)
	 *	10-> 1010 (2 个计算置位，2 是质数)
	 *
	 *	示例 2:
	 *	输入: L = 10, R = 15
	 *	输出: 5
	 *	解释:
	 *	10 -> 1010 (2 个计算置位, 2 是质数)
	 *	11 -> 1011 (3 个计算置位, 3 是质数)
	 *	12 -> 1100 (2 个计算置位, 2 是质数)
	 *	13 -> 1101 (3 个计算置位, 3 是质数)
	 *	14 -> 1110 (3 个计算置位, 3 是质数)
	 *	15 -> 1111 (4 个计算置位, 4 不是质数)
	 *	注意:
	 *	L, R 是 L <= R 且在 [1, 10^6] 中的整数。
	 *	R - L 的最大值为 10000。
	 * @param L
	 * @param R
	 * @return
	 */
	public int countPrimeSetBits(int L, int R) {
		// 20 以内的质数 2,3,5,7,11,13,17,19
		int count = 0;
		for (int i = L; i <= R; i++) {
			int cnt = 0;
			int j = i;
			while (j > 0) {
				j = j & (j - 1);
				cnt++;
			}
			if (cnt == 2 || cnt == 3 || cnt == 5 || cnt == 7 || cnt == 11 || cnt == 13 || cnt == 17 || cnt == 19) {
				count++;
			}
		}
		return count;
	}
    
    
    public static void main(String[] args) {
		System.out.println(Integer.toBinaryString(1000000).length());
	}
}
